With the rapid development of networks in recent years, opportunities have increased for one transmitting node to transmit the same packet to a plurality of receiving nodes, as in the case of video conferencing, network gaming, and so forth. In such cases, a transmitting node often performs distribution by means of multicast communication, which enables the same packet to be transmitted efficiently to all receiving nodes. For example, a transmitting node divides receiving nodes comprising packet distribution destinations into groups composed of around ten receiving nodes, and distributes a packet to each group by means of multicast communication.
One communication method that performs multicast communication on a group-by-group basis is an explicit multicast method. With an explicit multicast method, a transmitting node explicitly specifies all receiving nodes by entering the addresses of all the receiving nodes in a group in a packet option header or pilot. A typical explicit multicast method is XCAST (Explicit Multicast) (see Non-patent Document 1).
Generally, when multicast communication is performed to receiving nodes in the same group, all packet relay apparatuses (hereinafter referred to as “routers”) in a route must be compatible with multicast communication However, with an explicit multicast method, a transmitting node can distribute a packet to all receiving nodes whose addresses are entered in the packet even if all routers in a route are not compatible with an explicit multicast method. At this time, a bit sequence (hereinafter referred to as “bitmap”) in the packet header performs management of whether or not the packet has been distributed for each receiving node.
Here, a packet distribution method in explicit multicast communication will be described separately for a case in which all routers in a route are compatible with an explicit multicast method, and a case in which they are not. A packet is also distributed to all receiving nodes by means of the same kind of distribution method when only some of the routers in a route are compatible with an explicit multicast method.
On receiving a packet from another node, a router that is compatible with an explicit multicast method (hereinafter referred to as “compatible router”) searches the unicast route table of the router for all destination addresses entered in the packet option header or pilot to check a transmission interface corresponding to each destination address. Next, the compatible router duplicates the packet a number of times equivalent to the number of transfer destination interfaces, and transmits a packet corresponding to each interface. At this time, the compatible router scans a bitmap in the header for each duplicated packet, and adds a distribution-completed mark to a bit corresponding to a receiving node not included in the transfer destination interfaces. Furthermore, the compatible router rewrites a destination address entered in the IP header as a destination address of a distribution-unperformed receiver. Through repeated packet duplication and transmission by compatible routers in a route in this way, a packet is distributed to all receiving nodes.
Meanwhile, a router that is not compatible with an explicit multicast method (hereinafter referred to as “non-compatible router”), on receiving a packet from another node, does not reference a destination address entered in the packet option header or pilot, but transmits a packet in the same way as in ordinary unicast communication by searching the unicast route table of the router for a destination address entered in the IP header. On receiving a packet, a receiving node scans a bitmap in the header, and checks for the presence of a distribution-unperformed destination address. If there is a distribution-unperformed destination address, the receiving node duplicates a packet in which the IP header destination address has been rewritten as a distribution-unperformed destination address, and transmits this to a router. At this time, the receiving node adds a distribution-completed mark to a bit corresponding to itself contained in the bitmap. By having a receiving node that has received a packet transmit the received packet to a router again in this way, a packet is transferred to all receiving nodes. This kind of distribution is called “daisy-chain distribution”.
Using the above approach, a packet can be distributed to all receiving nodes by means of an explicit multicast method even if not all routers in a route are compatible with an explicit multicast method. Therefore, if an explicit multicast method is used, multicast communication can be performed using the Internet without replacing all routers in a route on the Internet with compatible routers.
Generally, in the event of congestion or the like in network communication, a packet traveling on the network may be lost (hereinafter referred to as “packet loss”). If a packet loss occurs in communication in which data must not be lost, such as a file transfer, a receiving node requests the transmitting node to retransmit a packet for which a packet loss occurred. However, in multicast communication, if all receiving nodes detecting a packet loss make a retransmission request to the transmitting node, there is a problem of an increased load on the transmitting node that receives the transmission requests, which affects normal communication. The following two methods whereby a receiving node makes a retransmission request to a node other than the transmitting node have been disclosed as solutions to this problem.
The first method is to provide an intermediate node for retransmission in a network. A receiving node that detects a packet loss makes a retransmission request to an intermediate node using multicast communication. An intermediate node that receives a retransmission request retransmits a packet to the receiving node that made the retransmission request using unicast communication or multicast communication (see Patent Document 1, for example).
The second method is to make a retransmission request without providing an intermediate node in a network. A receiving node that detects a packet loss waits for a random time before making a retransmission request to all receiving nodes by means of multicast communication. A receiving node that receives a retransmission request transmits a retransmission packet by means of multicast communication in accordance with a predetermined probability. If a receiving node receives a retransmission packet from another receiving node before retransmitting a packet itself, it does not transmit a retransmission packet despite receiving a retransmission request. Also, even if a receiving node detects a packet loss, it does not transmit a retransmission packet if a retransmission packet arrives by means of multicast communication during the wait time until transmission of a retransmission request (see Non-patent Document 2, for example).
Receiving nodes using these methods cannot know the IP address of another receiving node participating in multicast communication. Therefore, a receiving node that detects a packet loss transmits a retransmission request packet to another node using multicast communication, not unicast communication.
Through the use of these methods, even if a packet loss occurs in multicast communication, a receiving node can make a retransmission request to another node (intermediate node or receiving node) without imposing a load on the transmitting node.
Patent Document 1: Japanese Patent Application Laid-Open No. 2001-103051
Non-patent Document 1: Y. Imai, M. Shin and Y. Kim, “XCAST6: eXplicit Multicast on IPv6”, IEEE/IPSJ SAINT2003 Workshop 4, IPv6 and Applications, Orland, January 2003.
Non-patent Document 2: Sally Floyd, Van Jacobson, Ching-Gung Liu, Steven McCanne and Lixia Zhang, “A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing”, IEEE/ACM Transactions on Networking, Vol. 5, No. 6, December 1997.